package offer;

import java.util.ArrayList;

//最小的K个数
public class T30 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        class BigHeap {
            private  int heap[];
            private int size;
            public BigHeap(int size) {
                this.size = size;
                heap = new int[size];
            }
            public void buildHeap(int obj[]){
                for (int i=0;i<size;i++) heap[i] =obj[i];
                for (int i = size/2; i >=0 ; i--) {
                    shiftDown(i);
                }
            }
            public void shiftDown(int root) {
                 int left = (root<<1)+1;
                 int right = (root<<1)+2;
                 int max = root;
                 if (left<size&&heap[left]>heap[max]) max = left;
                 if (right<size&&heap[right]>heap[max]) max = right;
                 if (root!=max) {
                     swap(heap,root,max);
                     shiftDown(max);
                 }
            }
            public void shiftUp(int root) {
                int father = (root-1)>>1;
                if (father==0) return;
                if (heap[root]>heap[father]) {
                    swap(heap,root,father);
                    shiftUp(father);
                }
            }
            public void swap(int obj[],int i,int j) {
                int temp = obj[i];
                obj[i] =obj[j];
                obj[j]=temp;
            }
            public int getTop() {
                return heap[0];
            }
            public void  repalceTop(int num) {
                heap[0] = num;
                shiftDown(0);
            }
            public int[] getHeap() {
                return this.heap;
            }
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>(k);
        if (input==null||k>input.length||input.length<=0||k<=0) return arrayList;
        if (k==input.length) {
            for (int i = 0; i < input.length; i++) {
                arrayList.add(input[i]);
            }
            return arrayList;
        }
        BigHeap heap = new BigHeap(k);
        heap.buildHeap(input);
        for (int i = k; i < input.length; i++) {
            if (input[i]<heap.getTop()) heap.repalceTop(input[i]);
        }
        for (int num:heap.getHeap()) {
            arrayList.add(num);
        }
        return arrayList;
    }
    public static void main ( String[] args) {
        System.out.println(new T30().GetLeastNumbers_Solution(new int[]{4,5,1,6,2,7,3,8},4));
    }
}
